package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code20
 * @Description 请实现一个函数用来匹配包含'. '和'*'的正则表达式。
 * 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。
 * 在本题中，匹配是指字符串的所有字符匹配整个模式。
 * 例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-15 9:22
 */
public class Code20 {
//    public boolean isMatch(String s, String p) { // 递归的方法。。咱着实不会这种方法
//        /*
//        在模式串为空之后 只需要查看s是否为空
//         */
//        if (p.equals("")) return s.equals(""); // 如果s为空则匹配成功，如果s非空则匹配失败
//        boolean firstMatch = s.length() != 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'); // 保存首元素是否一致
//        if (p.length() >= 2 && p.charAt(1) == '*') {
//            return isMatch(s, p.substring(2)) || firstMatch && isMatch(s.substring(1), p); // 匹配0次 || 匹配多次
//        } else {
//            return firstMatch && isMatch(s.substring(1), p.substring(1));
//        }
//    }

    public static boolean firstMatch(String s, String p, int i, int j) {
        return s.charAt(i) == p.charAt(j) || p.charAt(j) == '.';
    }

    public static boolean isMatch(String s, String p) { // 使用动态规划的思路，填表格就可以了
        /*
        1. 首先需要创建规格为 (s.length + 1) * (p.length + 1) 的二维数组matrix，matrix[i, j] 代表 s的前i个字符和p的前j个字符的匹配情况
         */
        boolean[][] matrix = new boolean[s.length() + 1][p.length() + 1];

        /*
        2. 接下来对二维数组进行一些必要的初始化操作
         */
        matrix[0][0] = true; // 空串和空串成功匹配
        for (int i = 1; i < s.length() + 1; i++) { // 代表模式串为空，匹配串除了空之外全部匹配失败
            matrix[i][0] = false;
        }
        for (int i = 1; i < p.length() + 1; i++) { // 代表匹配串为空，在模式串出现*的情况下可能出现匹配0次而成功匹配空串的情况
            /*
            
            第i个字符若不是'*'则必定不可能和空串匹配成功，若为'*'的话，也应该在前面字符串匹配成功的情况下才可以匹配成功
             */
            matrix[0][i] = p.charAt(i - 1) == '*' && matrix[0][i - 2];
        }

        /*
        3. 接下来就是对二维数组逐行逐列赋值赋值
         */
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < p.length() + 1; j++) {
                if (p.charAt(j - 1) == '*') {
                    /*
                    匹配0次 || 匹配多次
                     */
                    matrix[i][j] = matrix[i][j - 2] || firstMatch(s, p, i - 1, j - 2) && matrix[i - 1][j];
                } else {
                    /*
                    第i个和第j个匹配，并且前i个和前j个也匹配时为true,否则为false
                     */
                    matrix[i][j] = firstMatch(s, p, i - 1, j - 1) && matrix[i - 1][j - 1];
                }
            }
        }
        return matrix[s.length()][p.length()];
    }

    public static void main(String[] args) {
        String s = "ab";
        String p = ".*";
        System.out.println(isMatch(s, p));
    }

}
